package src.tree;

public class no104 {//二叉树最大深度，递归法
/*    结点深度：root到该node的深度
    结点高度：该node到叶子的高度
    注：二叉树的最大深度 就是 root根节点的高度
    前序 求的是深度，后序 求的是高度*/

    public int maxDepth(TreeNode root) {
        //return getMaxDepth(root);

        getHeight(root,1);
        return height;

    }

    //后序遍历
    public int getMaxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = getMaxDepth(root.left);
        int right = getMaxDepth(root.right);
        return Math.max(left, right) + 1;
    }

    //前序遍历
    int height=0;  //全局变量height记录树高
    public void getHeight(TreeNode root, int n) {
        if (root == null) return;
        if(n>height) height = n;
        getHeight(root.left, n+1);
        getHeight(root.right, n+1);

    }

    /* 总结：两种常用处理方式
    *  1、自顶向下传递参数，对应先序遍历
    *  2、自底向上传递传递函数返回值，对应后序遍历
    * */
}
